It is common for electronic documents to contain curved lines (e.g. vector graphics) which may then have a dash pattern applied to them. The lines may need to be stroked, meaning that the ‘brush stroke’ width of the line or the dash pattern is changed. Subject to the length of the dash pattern relative to the brush stroke, and the width such a brush stroke creates, the dash pattern may appear either in-line with or transverse the curved line. When these documents need to be rendered for reproduction by a reproduction device, such as for display or for printing by a computing system, it is often necessary to convert the curves into a series of connected vectors (straight lines) which is then labelled as a path. Since the curve is approximated by a series of straight lines, there exists a level of error between the approximated path and the original curve. Existing computing systems, particularly in Raster Image Processors (RIP), approximate the curve based on a parameter known as the ‘flatness tolerance’, which defines the maximum amount of error the approximated path can deviate away from the original curve. The flatness tolerance is generally chosen such that the errors between the original curve and the approximated path of lines are not noticeable to the end user. The approximated path of straight lines is typically subdivided into dash and gap sections according to a given dash pattern, and each dash end, or endcap, is typically stroked by taking the perpendicular of the approximated path.
However, this approach can cause noticeable errors in the final appearance of the curve. For example, two dash ends located very near to each other on the curve with flat style endcaps should generally have nearly parallel endcaps, but when those two ends are located on two different straight lines, the endcaps will be sloped according to the different angles of the straight lines, and may intersect or otherwise have an incorrect appearance. Alternatively, if those two dash ends happen to be located on the same straight line, their endcaps will incorrectly be exactly parallel.
These problems are generally magnified further when the stroke width is large relative to the dash or gap length.
A common approach to avoid these issues is to increase the number of straight lines in the approximated curve. While this approach lessens the problem, it is not eliminated. Further, this approach increases the complexity of the approximate path and the eventual stroked path, thereby increasing the computational overhead and thus slowing down the processing of the curve.
Another approach suitable for certain types of curves is to directly calculate, for each pixel in the neighbourhood of a stroked dash, whether the pixel lies inside or outside the ideal dash outline. However, in many systems, particularly print rendering systems, the hardware capabilities available are insufficient to apply this method with acceptable performance.
Thus there exists a need to overcome, or at least ameliorate, the disadvantage of existing dashed curve approximation algorithms used in computing systems, and in particular RIPs.